#include "decoder.h"

Decoder::Decoder(qlonglong n, qlonglong k, QObject *parent) :
  QObject(parent),
  m_n(n),
  m_k(k),
  m_q(n+1),
  m_r(n-k),                // r = d − 1
  m_d(m_r+1),              // d = 2*t + 1
  m_t( (m_d - 1) / 2 ),
  m_gf(37),                // инициализировать поле
  m_g(1, 1)
{
#ifdef ERRS
  if ( n <= 0 || k <= 0 || n <= k ) { // проверка предусловия
    error("Decoder::Decoder(): код задан некорректно.");
  }
#endif

  // создание генераторного полинома
  for (int i = 0; i < m_r; ++i) {
    m_g = m_gf.conv( m_g, QVector<qlonglong>() << m_gf.alog(i) << m_gf.alog(0) );
  }
}

// декодировать
// предусловие: входной вектор должен быть длинны m_n
//// постусловие: кодовое слово должно делиться на генераторный полином без остатка
// постусловие: выходной вектор должен быть длинны m_k
QVector<qlonglong> Decoder::decode(QVector<qlonglong> b) {
#ifdef ERRS
  if ( b.size() != m_n ) { // проверка предусловия
    error("Decoder::decode(): длинна входного вектора не m_n.");
  }
#endif
  Deconv res;

  // вычисление синдрома
  QVector<qlonglong> synd = syndrome(b);

  QVector<qlonglong> a; // исправленное кодовое слово

  // если синдром не пуст => ошибок были
  if ( m_gf.trunc(synd) != (QVector<qlonglong>() << 0) ) {
    // нахождение полинома локаторов ошибок и полинома величин искажений
    QVector<qlonglong> valErrorsPoly; // полином величин искажений
    QVector<qlonglong> locatorPoly = euclideanAlgorithm(synd, valErrorsPoly);

    // вычисление локаторов ошибок
    QVector<qlonglong> locators = chienSearch(locatorPoly);

    // если локаторов меньше чем степень полинома локаторов ошибок
    if ( locators.size() != locatorPoly.size()-1 ) {
      // корни не найти => произошло больше чем t ошибок => исправить не можем
      a = b;
    }
    else {
      // вычисление значений ошибок
      QVector<qlonglong> errors = forneyAlgorithm(valErrorsPoly,
                                                  // производная полинома локаторов ошибок
                                                  m_gf.derivative(locatorPoly),
                                                  locators);
      // исправление ошибок
      a = errorCorrection(b, locators, errors);
    }
  }
  else {
    a = b;
  }

  // декодирование
  res = m_gf.deconv(a, m_g);

  // ?????????????? КОСТЫЛЬ
  // дополнить нулями если надо
  while (res.div.size() < m_k) {
    res.div.append(0);
  }
#ifdef ERRS
//  if ( res.mod != (QVector<qlonglong>() << 0) ) { // проверка постусловия
//    error("Decoder::decode(): исправленное слово не делиться на генераторный полином "
//          "без остатка.");
//  }
  if ( res.div.size() != m_k ) { // проверка постусловия
    error("Decoder::decode(): длинна выходного вектора не m_k.");
  }
#endif

  return res.div;
}

// вычисление синдрома
QVector<qlonglong> Decoder::syndrome(const QVector<qlonglong> b) {
  QVector<qlonglong> res; // синдром

  // !!!!!!!!!! возможно стоит отдельно хранить корни генераторного полинома
  for (int i = 0; i < m_r; ++i) { // перебор корней генераторного полинома
    res.append(  m_gf.substitute( b, m_gf.alog(i) )  ); // добавить синдромную компоненту
  }

  return res;
}

// Алгоритм Евклида - нахождение полинома локаторов ошибок и полинома величин искажений
QVector<qlonglong> Decoder::euclideanAlgorithm(QVector<qlonglong> syndrome,
                                               QVector<qlonglong> &valErrorsPoly) {
  QVector<qlonglong> r;               // делимое
  QVector<qlonglong> rOld(m_d, 0);
  QVector<qlonglong> s;               // делитель
  QVector<qlonglong> sOld;
  Deconv             q;               // частное и остаток
  QVector<qlonglong> res;             // в последствии полином локаторов ошибок
  QVector<qlonglong> resOld(1, 1);
  QVector<qlonglong> resOldOld(1, 0);

  rOld[m_d-1] = 1;                       // x^{m_d-1}
  // !!!!!!!!!!!!!!!!! возможно стоить переделать функцию деления gf.deconv для работы
  //                   с не сокращенными полиномами
  // !!!!!!!!!!!!!!!!! возможно имеет смысл оставлять вектора пустыми если там все нули
  sOld = m_gf.trunc(syndrome);

  while ( sOld.size()-1 > m_t ) {
    q   = m_gf.deconv(rOld, sOld);                  // q_i       = r_i / s_i

    r   = sOld;                                     // r_{i+1}   = s_i
    s   = q.mod;                                    // s_{i+1}   = r_i       - q_i * s_i
    res = m_gf.add(  resOldOld,                     // res_{i+1} = res_{i-1} - q_i * res_i
                     m_gf.conv( q.div, resOld )  );

    rOld      = m_gf.trunc(r);
    sOld      = m_gf.trunc(s);
    resOldOld = m_gf.trunc(resOld);
    resOld    = m_gf.trunc(res);
  }

  valErrorsPoly = sOld; // полином величин искажений

  return resOld;
}

// Поиск Ченя - вычисление локаторов ошибок
// предусловие: степень полинома локаторов ошибок не должна превышать корректирующую
//              способность кода
// постусловие: число корней должно быть равно степени полинома локаторов ошибок
QVector<qlonglong> Decoder::chienSearch(QVector<qlonglong> locatorPoly) {
  qlonglong t = locatorPoly.size() - 1; // число совершенных ошибок

#ifdef ERRS
  if ( t > m_t ) { // проверка предусловия
    error("Decoder::chienSearch(): степень полинома локаторов ошибок превышает "
          "корректирующую способность кода.");
  }
#endif

  QVector<qlonglong> res; // вектор локаторов ошибок

  // корня 0 быть не может, т.к. тогда позиция = -inf
  for (int i = 1; i < m_q && res.size() < t; ++i) { // перебор элементов поля
    if ( m_gf.substitute(locatorPoly, i) == 0 ) { // если корень
      // !!!!!!!!!! кокой смысл обращать? должно как-то просто находиться
      res.append( m_gf.amul(i) ); // добавить локатор
    }
  }

#ifdef ERRS
//  if ( res.size() != t ) { // проверка постусловия
//    // произошло больше чем t ошибок, корни начали повторяться
//    error("Decoder::chienSearch(): поиск Ченя не нашел требуемое число корней.");
//  }
#endif

  return res;
}

// Метод Форни - вычисление значений ошибок
// постусловие: значения ошибок должны быть не нулевыми
QVector<qlonglong> Decoder::forneyAlgorithm(QVector<qlonglong> valErrorsPoly,
                                            QVector<qlonglong> derivLocatorPoly,
                                            QVector<qlonglong> locators) {
  QVector<qlonglong> res;
  qlonglong denominator; // знаменатель
  qlonglong numerator;   // числитель
  for (int i = 0; i < locators.size(); ++i) {
    denominator = m_gf.substitute(  derivLocatorPoly, m_gf.amul( locators.at(i) )  );
    numerator   = m_gf.substitute(  valErrorsPoly,    m_gf.amul( locators.at(i) )  );
    // !!!!!!!!!!!!!! не уверен в степени локатора ошибок, для разных l0 должно быть
    // по разному говорят расписано в Кларке Кейне
    numerator   = m_gf.mul(  numerator, m_gf.power( locators.at(i), 1 - 0 )  );
#ifdef ERRS
    if (numerator == 0) { // проверка постусловия
      error("Decoder::forneyAlgorithm(): ошибка имеет значение 0.");
    }
#endif

    res.append( m_gf.div(numerator, denominator) ); // добавить значение ошибки
  }

  return res;
}

// исправление ошибок
QVector<qlonglong> Decoder::errorCorrection(QVector<qlonglong> b,
                                            QVector<qlonglong> locators,
                                            QVector<qlonglong> errors) {
  // исправление полученного кодового слова
  for (int i = 0; i < locators.size(); ++i) {
    int k = m_gf.log( locators.at(i) );
    b[k]  = m_gf.plus( b.at(k), errors.at(i) );
  }

  return b;
}
